package _73

/*
时间复杂度：O()
空间复杂度：O()

*/

func getDistances(arr []int) []int64 {
	hash := make(map[int][]int)
	hIndex := make(map[int]int)
	for i, v := range arr {
		if _, ok := hash[v]; !ok {
			hash[v] = []int{i}
			hIndex[v] = 0
		} else {
			hash[v] = append(hash[v], 0)
			n := len(hash[v])
			hash[v][n-1] = i + hash[v][n-2]
		}
	}
	result := make([]int64, 0)
	for i, v := range arr {
		index := hIndex[v]
		hIndex[v]++
		indexArr := hash[v]
		var count int64
		if index > 0 {
			count += int64((index * i) - indexArr[index-1])
		}
		n := len(indexArr)
		if index < n {
			count += int64(indexArr[n-1] - indexArr[index] - (n-1-index)*i)
		}
		result = append(result, count)
	}
	return result
}
